International Publication No. WO2009/110445 (Patent Document 1) and Japanese Patent Application Laid-Open Publication No. 2011-229093 (Patent Document 2) describe a method of processing a packet by using two tables. In one table, information such as an IP address is controlled with a hash value. In the other table, information such as an IP address is controlled by using a CAM. When a collision of a hash value is caused in registering the information such as the IP address, the information such as the IP address is registered in the table using the CAM.
Also, Japanese Patent Application Laid-Open Publication No. 2002-334114 (Patent Document 3) describes a method of dividing a MAC address table into a plurality of banks in order to reduce a probability of occurrence of rehash so that entry of each of the banks is simultaneously accessed by using a hash value of a MAC address as an address. Each entry contains an address bit (one bit) indicating an access history and a valid bit (one bit) indicating whether the entry is valid/invalid. When all valid bits of the respective entries corresponding to a certain hash value indicate valid, there is no vacant entry, and therefore, rehash for changing a hash function so as to perform the registration again is performed.